package sort;

/**
 * 快速排序
 *
 * @author zj
 */
@SuppressWarnings("all")
public class QuickSort<T extends Comparable<T>> implements Sort<T> {

    @Override
    public void sort(T[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(T[] arr, int startIndex, int endIndex) {
        if (arr == null || arr.length == 0 || startIndex < 0 || endIndex >= arr.length
                || startIndex > endIndex) {
            return;
        }
        int i = startIndex;
        int j = endIndex;
        T key = arr[i];
        while (i < j) {
            while (i < j && arr[j].compareTo(key) >= 0) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i].compareTo(key) <= 0) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;
        quickSort(arr, startIndex, i - 1);
        quickSort(arr, i + 1, endIndex);
    }
}
